package simple;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/4/15 21:05
 */
public class No496_下一个更大元素I {
    public static void main(String[] args) {
        Solution496 solution496 = new Solution496();
        int[] nums1 = new int[]{4, 3, 1};
        int[] nums2 = new int[]{3, 6, 4, 1, 8, 2};
        int[] ints = solution496.nextGreaterElement(nums1, nums2);
        System.out.println(ints);
    }
}

class Solution496 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //单调栈
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        //遍历nums2,获取元素的下一个更大
        for (int num2 : nums2) {
            //pop情况
            while (!stack.isEmpty() && num2 > stack.peek()) {
                //正在泰山压顶....
                //统统出去,并诅咒之
                Integer pop = stack.pop();
                map.put(pop, num2);
            }
            //push情况
            stack.push(num2);
        }
        
        //顽固的罗汉处理
        while (!stack.isEmpty()) {
            map.put(stack.pop(), -1);
        }
        
        //最后,对nums1每个元素从map获取下一个元素
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = map.get(nums1[i]);
        }
        return nums1;
    }
}



    //public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    //    //暴力法
    //    int[] res = new int[nums1.length];
    //    for (int i = 0; i < nums1.length; i++) {
    //        //4
    //        int base = nums1[i];
    //        //找base在nums2的位置
    //        out:for (int j = 0; j < nums2.length; j++) {
    //            //处理j为最后的情况,直接返回-1
    //            if (nums2.length - 1 == j) {
    //                res[i] = -1;
    //            }
    //
    //            if (base == nums2[j]) {
    //                //位置找到,继续找下一个更大的位置k
    //                for (int k = j + 1; k < nums2.length; k++) {
    //                    if (nums2[k] > base) {
    //                        res[i] = nums2[k];
    //                        break out;
    //                    }
    //                }
    //            }
    //        }
    //    }
    //    return res;
    //}




